- Title
- Quadratic kernelization for convex recoloring of trees
- Creator
- Bodlaender, Hans L.; Fellows, Michael R.; Langston, Michael A.; Ragan, Mark A.; Rosamond, Frances A.; Weyer, Mark
- Relation
- Algorithmica Vol. 61, Issue 2, p. 362-388
- Publisher Link
- http://dx.doi.org/10.1007/s00453-010-9404-2
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2011
- Description
- The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/logk)k n 4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k²).
- Subject
- algorithms; combinatorial algorithms; fixed parameter tractability; kernelization; convex recoloring; trees; phylogeny
- Identifier
- http://hdl.handle.net/1959.13/936218
- Identifier
- uon:12243
- Identifier
- ISSN:0178-4617
- Language
- eng
- Reviewed
- Hits: 3947
- Visitors: 4230
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|